package com.vint.leetcode;

import com.vint.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/*
 * 1. done
 * 2. easy
 * 3. tree,
 * 二叉树层次遍历
 */
public class Leetcode105 {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return buildSub(preorder, 0 , preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	public TreeNode buildSub(int[] pre, int ps, int pe, int[] ino, int is, int ie) {
		if (pe < ps) return null;
		TreeNode root = new TreeNode(pre[ps]);
		if(pe == ps) return root;
		int index = 0;
		for(int i = is; i<=ie; i++){
			if(ino[i] == pre[ps]){
				index = i;
				break;
			}
		}
		root.left = buildSub(pre, ps + 1, ps  + index - is, ino, is, index -1);
		root.right= buildSub(pre, ps  + index - is + 1, pe,  ino, index + 1,ie);
		return root;
	}
}
